//二叉树的深度: https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?
//方法一
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
  public:
    void TreeDepthHelper(TreeNode* pRoot, int curr, int& max) {
        if (pRoot == nullptr) 
		{
            if (max < curr) 
			{
                max = curr;
            }
            return;
        }
        TreeDepthHelper(pRoot->left, curr + 1, max);
        TreeDepthHelper(pRoot->right, curr + 1, max);
    }

    int TreeDepth(TreeNode* pRoot) 
	{
        if (pRoot == nullptr) 
		{
            return 0;
        }
        int depth = 0;
        int max = 0;
        TreeDepthHelper(pRoot, depth, max);
        return max;
    }
};
//方法二
class Solution {
  public:
    int TreeDepth(TreeNode* pRoot) 
	{
        if (pRoot == nullptr) 
		{
            return 0;
        }
        return 1 + max(TreeDepth(pRoot->left), TreeDepth(pRoot->right));
    }

};
//方法三，层序遍历
class Solution {
  public:
    int TreeDepth(TreeNode* pRoot) {
        if (pRoot == nullptr) 
		{
            return 0;
        }
		//层序大法好
        queue<TreeNode*> q;
        q.push(pRoot);
        int depth = 0;
        while (!q.empty()) 
		{
			//每次把当前层全部处理完，切记
            int size = q.size();
            depth++; //每次处理一层，只要还在处理，就说明深度在递增
            for (int i = 0; i < size; i++) 
			{ 
				//处理完本层，压人下一层
                TreeNode* curr = q.front();
                q.pop(); //去掉当前节点
                if (curr->left) q.push(curr->left);
                if (curr->right) q.push(curr->right);
            }
        }
        return depth;
    }
};